// 5.最长回文子串
package LeetcodeHot100;

public class Solution005 {
    public String longestPalindrome(String s) {
        int index = 0;
        int max = 1;

        boolean[][] dp = new boolean[s.length()][s.length()];

        for (int len = 1; len <= s.length(); len++) {
            for (int cur = 0; cur + len <= s.length(); cur++) {
                if (len == 1)
                    dp[cur][cur + len - 1] = true;
                else if (len == 2)
                    dp[cur][cur + len - 1] = s.charAt(cur) == s.charAt(cur + len - 1);
                else
                    dp[cur][cur + len - 1] = s.charAt(cur) == s.charAt(cur + len - 1) ? dp[cur + 1][cur + len - 2]
                            : false;
                if (dp[cur][cur + len - 1] == true && len > max) {
                    max = len;
                    index = cur;
                }
            }
        }

        return s.substring(index, index + max);
    }
}
